import { btPrint } from "hy-algokit";

class Node<T> {
  value: T;
  constructor(value: T) {
    this.value = value;
  }
}

export class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent: TreeNode<T> | null = null;
  get isLeft() {
    return !!(this.parent && this.parent.left === this);
  }
  get isRight() {
    return !!(this.parent && this.parent.right === this);
  }
}

export class BSTree<T = number> {
  protected root: TreeNode<T> | null = null;

  print() {
    return btPrint(this.root);
  }

  protected createNode(value: T): TreeNode<T> {
    return new TreeNode<T>(value);
  }

  protected checkBalanced(node: TreeNode<T>, isAdd = true) {}

  // 插入函数
  insert(value: T) {
    const newNode = this.createNode(value);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }

    this.checkBalanced(newNode);
  }

  // 插入节点
  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
        newNode.parent = node; // 设置父节点
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
        newNode.parent = node; // 设置父节点
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 先序遍历
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }

  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }

  // 中序遍历
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }
  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left);
      console.log(node.value);
      this.inOrderTraverseNode(node.right);
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }

  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node !== null) {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }

  // 层序遍历
  levelOrderTraverse() {
    if (this.root === null) return;

    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    while (queue.length > 0) {
      const node = queue.shift()!;
      console.log(node.value);

      if (node.left !== null) {
        queue.push(node.left);
      }

      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }

  // 搜索节点
  search(value: T): boolean {
    return !!this.searchNode(value);
  }

  private searchNode(value: T): TreeNode<T> | null {
    if (this.root === null) return null;
    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.value === value) {
        return current;
      }
      parent = current;
      if (current.value < value) {
        current = current.right;
      } else {
        current = current.left;
      }

      if (current) current.parent = parent;
    }

    return null;
  }

  // 获取后继节点
  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
    // 从被删除节点的右子树开始
    let current = delNode.right;
    // 初始化后继节点为null
    let successor: TreeNode<T> | null = null;
    // 遍历右子树，找到最小的节点
    while (current) {
      successor = current;
      current = current.left;
      // 如果当前节点不为空，则将当前节点的父节点指向后继节点
      if (current) current.parent = successor;
    }

    // 删除后继节点
    // 如果后继节点不是被删除节点的右子节点，则将后继节点的左子树连接到被删除节点的右子树
    if (successor !== delNode.right) {
      successor!.parent!.left = successor!.left;
      // successor!.right = delNode.right;
      if (successor!.right) {
        // 将被删除节点的右子树连接到后继节点的右子树
        successor!.right!.parent = successor!.parent;
      }
    } else {
      delNode.right = successor!.right;
    }

    // 将被删除节点的左子树连接到后继节点的左子树
    // successor!.left = delNode.left;

    // 返回后继节点
    return successor!;
  }

  // 删除节点
  remove(value: T): boolean {
    // 搜索要删除的节点
    const current = this.searchNode(value);
    // 如果找不到要删除的节点，返回false
    if (!current) return false;

    // 要删除的节点
    let delNode: TreeNode<T> = current;

    // 替换节点
    let replaceNode: TreeNode<T> | null = null;
    // 如果要删除的节点没有左子节点和右子节点，替换节点为null
    if (current.left === null && current.right === null) {
      replaceNode = null;
      // 如果要删除的节点没有右子节点，替换节点为左子节点
    } else if (current.right === null) {
      replaceNode = current.left;
      // 如果要删除的节点没有左子节点，替换节点为右子节点
    } else if (current.left === null) {
      replaceNode = current.right;
      // 如果要删除的节点既有左子节点又有右子节点，替换节点为后继节点
    } else {
      const successor = this.getSuccessor(current);
      // replaceNode = successor;
      current.value = successor.value;
      delNode = successor;
      // 检查平衡
      this.checkBalanced(delNode, false);
      return true;
    }

    // 如果要删除的节点是根节点，将根节点替换为替换节点
    if (current === this.root) {
      this.root = replaceNode;
      // 如果要删除的节点是左子节点，将父节点的左子节点替换为替换节点
    } else if (current.isLeft) {
      current.parent!.left = replaceNode;
      // 如果要删除的节点是右子节点，将父节点的右子节点替换为替换节点
    } else {
      current.parent!.right = replaceNode;
    }

    // 如果替换节点是后继节点，将后继节点的右子节点替换为要删除的节点的右子节点
    if (replaceNode && current.parent) {
      replaceNode.parent = current.parent;
    }

    return false;
  }
}

export {};
